DAY 6 試題

(由於此題為上鎖題，因此題目只能從網路分享看到)

問題描述

給定一個由 n 個節點（標號為 0 到 n-1）和一個無向邊列表組成的圖，要求判斷這些邊是否能構成一棵有效的樹。

範例：

1. Input: n = 5
   edges = [[0,1], [0,2], [0,3], [1,4]]
   Output: true
   解釋: 這些邊構成了一棵樹，因為它包含了 n-1 條邊且無環。

2. Input: n = 5
   edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
   Output: false
   解釋: 這些邊包含了環，因此不是一棵樹。

限制條件：

• 節點的數量 n 在範圍 [1, 2000] 之間。
• 邊的數量 edges 不會重複，並且每個邊是無向的。

解題思路

樹的兩個關鍵性質是無環和連通性。基於這些特點，我們可以使用**深度優先搜索（DFS）**來解決問題：

1. 無環檢查：從任意節點出發，使用 DFS 尋找環。如果在遍歷過程中發現某個節點已經被訪問過，則表示存在環，無法構成樹。
2. 連通性檢查：遍歷結束後，檢查是否所有節點都被訪問過。如果有未訪問的節點，表示圖不是連通的，也無法構成樹。
3. 邊數檢查：樹必須有 n-1 條邊，這是構成樹的必要條件。如果邊數不是 n-1，則可以直接返回 false。

class Solution {
public:
    bool validTree(int n, vector<pair<int, int>>& edges) { 
        // 構建鄰接表來表示圖
        vector<vector<int>> g(n);
        vector<bool> visited(n, false);

        // 將邊加入到鄰接表
        for (auto& edge : edges) { 
            g[edge.first].push_back(edge.second); 
            g[edge.second].push_back(edge.first); 
        }

        // 如果 DFS 發現環，則不是樹
        if (!dfs(g, visited, 0, -1)) return false;

        // 檢查所有節點是否都被訪問過
        for (bool v : visited) {
            if (!v) return false;
        }

        return true;
    }

    // DFS 遍歷
    bool dfs(vector<vector<int>>& g, vector<bool>& visited, int cur, int parent) {
        if (visited[cur]) return false;  // 如果該節點已經被訪問，表示存在環
        visited[cur] = true;  // 標記當前節點已訪問

        // 遍歷當前節點的所有鄰居
        for (int neighbor : g[cur]) {
            if (neighbor != parent) {  // 不要訪問回來的父節點
                if (!dfs(g, visited, neighbor, cur)) return false;
            }
        }

        return true;
    }
};

解法步驟

1. 構建鄰接表：首先，我們根據邊列表構建圖的鄰接表表示。每個節點的鄰接節點存儲在一個向量中。
2. DFS 遍歷：從節點 0 開始使用 DFS，檢查是否有環。每次遞迴都記錄當前節點的狀態，如果再次訪問已經訪問過的節點，則說明有環存在。
3. 環檢查：如果 DFS 過程中發現了環，則返回 false，表示該圖不是一棵樹。
4. 連通性檢查：遍歷完畢後，檢查是否所有節點都已被訪問。如果存在未訪問的節點，說明圖不連通，返回 false。
5. 返回結果：如果既無環且所有節點都被訪問過，則圖是一棵有效的樹。

時間與空間複雜度分析

• 時間複雜度：構建圖的過程需要 O(n) 時間，DFS 遍歷圖的過程需要 O(n + e) 時間，其中 n 是節點數，e 是邊數。因此，總的時間複雜度是 O(n + e)。
• 空間複雜度：鄰接表使用 O(n) 空間來存儲每個節點的鄰居列表，DFS 過程中使用一個 visited 陣列來記錄訪問狀態，這些結構的空間複雜度也是 O(n)。

總結

這題的核心在於判斷一個無向圖是否構成一棵有效的樹，而樹的兩個基本性質是無環與連通性。為了驗證這兩點，我們選擇使用深度優先搜索（DFS）。DFS 的特點是從一個節點開始遍歷整個圖，能夠有效檢查是否有環出現，因為在遍歷過程中，如果再次訪問到已經訪問過的節點（且不是父節點），就說明存在環。同時，DFS 也可以幫助確認整個圖是否連通，因為在遍歷過程中，若有節點未被訪問，則說明圖不連通。這題的重點在於理解樹的性質，以及如何利用 DFS 來驗證無環性與連通性，確保圖的結構符合樹的定義。

以上是第六天的自學內容分享，謝謝大家。